Matrice d'adjacence - Comptage de chaînes (3)

Énoncé

Le lycée de Lucie est situé à Paris proche de la station de métro Invalides. Elle a fait un relevé du plan de métro simplifié du quartier en utilisant seulement les stations suivantes :

• Champs-Élysées Clemenceau (CE)
  
• Châtelet (CH)
• Concorde (CO)
• Duroc (D)
• Charles de Gaulle Etoile (E)
• Franklin Roosevelt (F)
• Invalides (I)
• Montparnasse (M)
• La Motte Piquet Grenelle (MP)
• Odéon (O)
• Pasteur (P)
• Sèvres Babylone (S)
• Trocadéro (T)
  

Voici le graphe qu'elle a dessiné.

1. Écrire la matrice d'adjacence de ce graphe (on notera les sommets dans l'ordre alphabétique des abréviations ci-dessus).

2. Donner un exemple de chaîne à 5 arêtes reliant Concorde et La Motte Piquet Grenelle.

3. Combien y a-t-il de chaînes à 5 arêtes reliant Concorde et La Motte Piquet Grenelle ?